/*
 * 最大流 说明
 */

#include <stdio.h>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
typedef int 	cap_type; 	//容量数据类型

class MaxFlow;

class Edge{
	friend MaxFlow;
private:
	int 		ed; 	//终点
	cap_type 	cap; 	//剩余容量
	cap_type 	init_cap; 	//初始容量
};

class MaxFlow{
private:
	int 	dot_num; 	//顶点数目
	int 	start_index; //顶点起始下标				
	int 	end_index;	 //顶点结束下标
	int 	edge_num;
	vector<Edge> 	edges; //边
	vector<int> 	que; 	//BFS搜索的队列
	vector<int> 	depth; 	//BFS记录的每顶点的深度
	vector<int> 	stack_edge_index; 	//模拟深搜记录每一层当前边的下标
	vector<int> 	stack_dot; 			//模拟深搜记录每一层访问的顶点
	vector<int> 	stack_edge; 		//模拟深搜记录每一层增广路的边
	vector<vector<int> > 	edge_map; 		//点和点之间的边下标
	vector<vector<int> > 	edge_index; 	//某个点流出的边的下标

	static const int 	MARK_EMPTY; //空标记
public:
	MaxFlow(int max_num){
		start_index = 0;
		edge_num = 0;
		dot_num = max_num;
		end_index = dot_num + start_index - 1;
		resize(end_index + 1);
	}

	void resize(int num){
		edges.resize(num);
		edge_map.resize(num);
		edge_index.resize(num);
		que.resize(num);
		depth.resize(num);
		stack_edge_index.resize(num);
		stack_dot.resize(num);
		stack_edge.resize(num);
		for(int i = start_index; i <= end_index; i++){
			edge_map[i].resize(end_index + 1);
		}
	}
	
	void init(int n){
		dot_num = n;
		edge_num = 0;
		end_index = n + start_index - 1;
		if(end_index + 1 > edges.size()){
			resize(end_index + 1);
		}
		for(int i = start_index; i <= end_index; i++){
			edge_index[i].clear();
			for(int j = start_index; j <= end_index; j++){
				edge_map[i][j] = MARK_EMPTY;
			}
		}
	}

	void add_edge(int st, int ed, cap_type cap){
		int edge = edge_map[st][ed];	
		if(edge == MARK_EMPTY){
			//添加新边和反向边
			if(edge_num + 2 > edges.size()){
				edges.resize(edge_num + 2);
			}
			edges[edge_num].ed = ed;
			edges[edge_num].cap = edges[edge_num].init_cap = cap;
			edge_map[st][ed] = edge_num;
			edge_index[st].push_back(edge_num);
			edge_num++;
				
			//反向边
			edges[edge_num].ed = st;
			edges[edge_num].cap = edges[edge_num].init_cap = 0;
			edge_map[ed][st] = edge_num;
			edge_index[ed].push_back(edge_num);
			edge_num++;
		}else{
			edges[edge].cap += cap;
			edges[edge_num].init_cap += cap;
		}
	}

	//获取最大流
	cap_type get_flow(int st, int ed){
		if(st == ed) return 0;
		cap_type flow = 0;
		//BFS标记depth数组		
		int l, r, cur, edge, next, stack_top, min_cap_edge, back_index;
		cap_type add_flow;
		while(true){
			for(int i = start_index; i <= end_index; i++){
				depth[i] = MARK_EMPTY;
			}
			l = 0;
			r = 1;
			que[l] = st;
			depth[st] = 1;
			while(l < r){
				cur = que[l++];
				for(int i = 0; i < edge_index[cur].size(); i++){
					edge = edge_index[cur][i];
					if(edges[edge].cap > 0 && depth[ edges[edge].ed ] == MARK_EMPTY){
						que[r++] = edges[edge].ed;
						depth[ edges[edge].ed ] = depth[cur] + 1;
					}
				}
			}
			if(depth[ed] == MARK_EMPTY) break;
			//模拟DFS
			stack_top = 0;  //栈顶
			stack_dot[stack_top] = st;
			stack_edge_index[stack_top] = 0;
			while(stack_top >= 0){
				cur = stack_dot[stack_top];	
				if(cur == ed){
					//找到一条增广路径
					min_cap_edge = MARK_EMPTY;
					back_index = 0;
					//printf("增广路:\n");
					for(int i = 0; i < stack_top; i++){
						edge = stack_edge[i];
						//printf("%d ", edges[edge].ed);
						if(min_cap_edge == MARK_EMPTY || edges[min_cap_edge].cap > edges[edge].cap){
							min_cap_edge = edge;
							back_index = i;
						}
					}
					if(min_cap_edge != MARK_EMPTY){
						add_flow = edges[min_cap_edge].cap;	
						flow += add_flow;
						for(int i = 0; i < stack_top; i++){
							edge = stack_edge[i];
							edges[edge].cap -= add_flow;
							edges[inv_edge(edge)].cap += add_flow;
						}
					}
					// printf("\nadd_flow:%d back_index:%d\n", add_flow, back_index);
					stack_top = back_index;
					continue ;
				}
				int k = stack_edge_index[stack_top];
				for(; k < edge_index[cur].size(); k++){
					edge = edge_index[cur][k];
					if(edges[edge].cap > 0 && depth[cur] + 1 == depth[ edges[edge].ed ]){
						//找到一条剩余容量大于0的边
						break;
					}
				}
				if(k >= edge_index[cur].size()){
					//边搜索完了，往上退一层
					stack_top--;
					continue;
				}
				stack_edge_index[stack_top] = k+1;
				stack_edge[stack_top] = edge;
				//新顶点入栈
				stack_top++;
				stack_dot[stack_top] = edges[edge].ed;
				stack_edge_index[stack_top] = 0;
			}
		}
		return flow;
	}
	
	//反向边的下标
	int inv_edge(int edge){
		return edge ^ 1;
	}

};
const int MaxFlow::MARK_EMPTY = -1;
int main(int argc, char* argv[])
{
	const int NUM = 20;
	int n, i, j, st, ed, k, g, f, r, c, sum;
	MaxFlow max_flow(NUM * NUM + 2);
	int around[4][2] = {
		{0, -1},
		{-1, 0},
		{0, 1},
		{1, 0},
	};
	int a[NUM][NUM];
	while(scanf("%d", &n) != EOF){
		max_flow.init(n * n + 2);	
		st = 0;
		ed = n * n + 1;
		sum = 0;
		for(i = 0; i < n; i++){
			for(j = 0; j < n; j++){
				scanf("%d", &f);
				sum += f;
				a[i][j] = f;
			}
		}
		for(i = 0; i < n; i++){
			for(j = 0; j < n; j++){
				k = i * n + j + 1;
				if((i + j) & 1){
					//右边的点
					max_flow.add_edge(k, ed, a[i][j]);
				}else{
					//左边的点
					max_flow.add_edge(st, k, a[i][j]);
					//左边的点往相邻的右边的点连边
					for(g = 0; g < 4; g++){
						r = i + around[g][0];
						c = j + around[g][1];
						if(r >= 0 && r < n && c >= 0 && c < n){
							max_flow.add_edge(k, r * n + c + 1, sum);
						}
					}
				}
			}
		}
		f = max_flow.get_flow(st, ed);
		printf("%d\n", sum - f);
	}
    return 0;
}
